package com.heima.leetcode.practice;

import java.util.HashMap;

/**
 * leetcode 460.LFU 缓存
 *
 * @author 勾新杰
 * @version 1.0
 * @date 2024/11/19 19:40
 */
public class E460 {
    // LFU是一种淘汰策略：
    // 1、访问次数最少的缓存项优先被淘汰。
    // 2、如果最少频率的缓存项有多个，则优先淘汰最久未使用的缓存项。
    //
    // 而设计LFU缓存的话，要保证获取、删除、更新缓存项都要达到O(1)的时间复杂度。
    // 不仅如此，还要实现最久未使用的淘汰策略
    // 所以要考虑使用哈希表+双向链表来实现。
    // 具体就是创建两个哈希表，一个是根据键来查找缓存项，另一个根据频次来查找缓存项。
    // 显然后者查出来的缓存项可能有多个，还要实现LRU策略，所以要用双向链表。

    /**
     * LFU缓存类
     */
    static class LFUCache {

        private final HashMap<Integer, CacheNode> caches; // 根据键查找缓存项的哈希表
        private final HashMap<Integer, DoublyLinkedList> frequencyCaches; // 按照频次分类好的缓存项形成的哈希表，键是频率，值是lruList
        private final int capacity; // 规定的最大缓存容量
        private int minFrequency; // 记录当前所有缓存项的最小频次

        /**
         * 构造函数初始化
         *
         * @param capacity 缓存容量
         */
        public LFUCache(int capacity) {
            this.caches = new HashMap<>();
            this.frequencyCaches = new HashMap<>();
            this.capacity = capacity;
        }

        /**
         * 双向链表缓存项节点类
         */
        static class CacheNode {
            CacheNode prev; // 前一个节点
            CacheNode next; // 后一个节点
            int key; // 键
            int value; // 值
            int frequency; // 频次

            /**
             * 无参构造
             */
            public CacheNode() {
            }

            /**
             * 有参构造
             *
             * @param key   键
             * @param value 值
             */
            public CacheNode(int key, int value) {
                this.key = key;
                this.value = value;
                this.frequency = 1;
            }
        }

        /**
         * 双向链表类
         */
        static class DoublyLinkedList {
            CacheNode head; // 头指针
            CacheNode tail; // 尾指针
            int size; // 大小

            /**
             * 无参构造
             */
            public DoublyLinkedList() {
                this.head = new CacheNode();
                this.tail = new CacheNode();
                head.next = tail;
                tail.prev = head;
            }

            /**
             * 头部添加缓存项
             *
             * @param node 缓存项
             */
            public void addFirst(CacheNode node) {
                CacheNode next = head.next;
                CacheNode prev = head;
                node.next = next;
                next.prev = node;
                node.prev = prev;
                prev.next = node;
                size++;
            }

            /**
             * 移除指定缓存项
             *
             * @param node 缓存项
             */
            public void remove(CacheNode node) {
                CacheNode prev = node.prev;
                CacheNode next = node.next;
                prev.next = next;
                next.prev = prev;
                size--;
            }

            /**
             * 移除尾部缓存项
             *
             * @return 移除的缓存项
             */
            public CacheNode removeLast() {
                CacheNode last = tail.prev;
                remove(last);
                return last;
            }

            /**
             * 判断是否为空
             *
             * @return true表示为空，false表示不为空
             */
            public boolean isEmpty() {
                return size == 0;
            }
        }

        /**
         * 获取缓存项的值
         *
         * @param key 键
         * @return 值，若不存在则返回-1
         */
        public int get(int key) {
            CacheNode node = caches.get(key);
            // 1. 该缓存项不存在
            if (node == null) {
                return -1;
            }
            // 2. 该缓存项存在
            else {
                // 2.1 在该频率对应的缓存项链表中移除该缓存项
                DoublyLinkedList lruList = frequencyCaches.get(node.frequency);
                lruList.remove(node);
                // 2.2 在该频率对应的缓存项链表如果变为空，则增加最小频率
                if (node.frequency == minFrequency && lruList.isEmpty()) minFrequency++;
                // 2.3 该缓存项的频次加一
                node.frequency++;
                // 2.4 在该频率+1对应的缓存项链表中头部添加该缓存项
                frequencyCaches.computeIfAbsent(node.frequency, k -> new DoublyLinkedList())
                        .addFirst(node);
                // 2.5 返回缓存项的值
                return node.value;
            }
        }

        /**
         * 添加缓存项
         *
         * @param key   键
         * @param value 值
         */
        public void put(int key, int value) {
            CacheNode node = caches.get(key);
            // 1. key对应的缓存项已经存在，说明是更新操作
            if (node != null) {
                // 1.1 更新缓存项的值
                node.value = value;
                // 1.2 从当前缓存项频率的链表中移除该缓存项
                DoublyLinkedList lruList = frequencyCaches.get(node.frequency);
                lruList.remove(node);
                // 1.3 如果最小频率等于当前缓存项的频次，并且移除后该链表为空，则最小频率加一
                if (minFrequency == node.frequency && lruList.isEmpty()) minFrequency++;
                // 1.4 将该缓存项的频次加一
                node.frequency++;
                // 1.5 将该缓存项加入到新的缓存项频率的链表头部
                frequencyCaches.computeIfAbsent(node.frequency, k -> new DoublyLinkedList())
                        .addFirst(node);
            }
            // 2. key对应的缓存项不存在，说明是插入操作
            else {
                // 2.1 新建缓存项
                node = new CacheNode(key, value);
                // 2.2 先看已经存在的缓存项是否已经达到容量上限
                if (caches.size() == capacity) {
                    // 2.2.1 获取最低频率使用的缓存项链表
                    DoublyLinkedList lruList = frequencyCaches.get(minFrequency);
                    // 2.2.2 移除最低频率所有缓存项中最久未使用的缓存项
                    CacheNode last = lruList.removeLast();
                    // 2.2.3 从缓存项哈希表中移除该缓存项
                    caches.remove(last.key);
                }
                // 2.3 在缓存项哈希表中插入新的缓存项
                caches.put(key, node);
                // 2.4 在频次为1的缓存项链表中添加该缓存项
                frequencyCaches.computeIfAbsent(1, k -> new DoublyLinkedList())
                        .addFirst(node);
                // 2.5 更新最小频次
                minFrequency = 1;
            }
        }
    }
}

